package org.zoomdev.zoom;

import java.nio.charset.StandardCharsets;
import java.util.Collection;
import java.util.Map;
import java.util.TreeMap;
import java.util.UUID;

public class ConsistentHashRing {
    private static final int RING_SIZE = Integer.MAX_VALUE; // 32位哈希空间
    private final TreeMap<Integer, String> ring = new TreeMap<>();

    public static void main(String[] args) {
        ConsistentHashRing ring = new ConsistentHashRing();

        // 添加初始节点
        ring.addNode("Node-A");
        ring.addNode("Node-B");
        ring.addNode("Node-C");
        ring.printRing();

        // 添加在Node-B之前的新节点
        ring.addNodeBefore("Node-D", "Node-B");
        ring.printRing();

        // 在环首节点前添加节点
        ring.addNodeBefore("Node-E", "Node-C");
        ring.printRing();
    }

    // 其他现有方法保持不变...
    public void addNode(String node) {
        int position = getDiscreteHash(node);
        ring.put(position, node);
    }

    // 辅助方法：打印环状态
    public void printRing() {
        System.out.println("\nCurrent Hash Ring:");
        ring.forEach((pos, node) ->
                System.out.printf("Position %10d: %s%n", pos, node));
        System.out.println();
    }

    // 新增方法：在指定节点之前添加新节点
    public void addNodeBefore(String newNode, String existingNode) {
        // 1. 验证已有节点是否存在
        Integer existingPosition = findNodePosition(existingNode);
        if (existingPosition == null) {
            throw new IllegalArgumentException("Existing node not found: " + existingNode);
        }

        // 2. 获取前驱节点位置
        Integer predecessorPosition = getPredecessorPosition(existingNode);

        // 3. 计算新节点位置
        int newPosition = calculatePositionBefore(existingPosition, predecessorPosition);

        // 4. 确保位置不冲突
        newPosition = resolvePositionConflict(newPosition);

        // 5. 添加新节点
        ring.put(newPosition, newNode);
        System.out.printf("Added node '%s' at position %d before '%s'%n",
                newNode, newPosition, existingNode);
    }

    /**
     * 高离散性哈希函数
     * 设计原则：
     * 1. 雪崩效应：输入微小变化导致输出剧烈变化
     * 2. 均匀分布：不同输入均匀分布在输出空间
     * 3. 低碰撞率：不同输入冲突概率极低
     * 4. 高效计算：时间复杂度O(n)
     */
    private int getDiscreteHash(String value) {
        // 空值处理
        if (value == null) return 0;

        byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
        int hash = 0x7a35_8a97; // 初始种子（素数）

        for (int i = 0; i < bytes.length; i++) {
            // 当前字节处理（扩展为32位无符号）
            int current = bytes[i] & 0xFF;

            // 1. 比特置换：增加扩散性
            current = Integer.reverseBytes(current) >>> 16;

            // 2. 混合当前字节
            hash ^= current;

            // 3. 乘法运算（使用大质数模2^32）
            hash *= 0x7ed55d16;

            // 4. 移位运算（使用黄金分割比旋转）
            hash = (hash << 7) | (hash >>> 25);

            // 5. 加法混合（使用π常数）
            hash += 0x4F1BBCDC;

            // 6. 每处理4个字节应用非线性变换
            if ((i & 3) == 3) {
                hash = nonLinearMix(hash);
            }
        }

        // 最终非线性增强
        return finalizeHash(hash);
    }

    // 查找节点位置
    private Integer findNodePosition(String node) {
        for (Map.Entry<Integer, String> entry : ring.entrySet()) {
            if (entry.getValue().equals(node)) {
                return entry.getKey();
            }
        }
        return null;
    }

    // 获取节点的前驱位置
    public int getPredecessorPosition(String node) {
        Integer position = findNodePosition(node);
        if (position == null) return -1;

        Integer predecessor = ring.lowerKey(position);
        return predecessor != null ? predecessor : ring.lastKey();
    }

    // 计算新节点位置
    private int calculatePositionBefore(int existingPos, int predecessorPos) {
        // 如果已有节点是环首（没有前驱）
        if (predecessorPos > existingPos) {
            // 环首节点前的特殊处理
            int gap = (RING_SIZE - predecessorPos) + existingPos;
            return (predecessorPos + gap / 2) % RING_SIZE;
        } else {
            // 正常情况：取现有节点和前驱节点中间值
            return (int) (((long) predecessorPos + existingPos) / 2);
        }
    }

    // 处理位置冲突
    private int resolvePositionConflict(int position) {
        int original = position;
        int attempts = 0;

        // 当位置已被占用时，尝试附近位置
        while (ring.containsKey(position)) {
            // 冲突解决策略：线性探测 + 二次哈希
            int step = (int) (Math.pow(2, attempts) + rehash(position));
            position = (original + step) % RING_SIZE;
            attempts++;

            // 防止无限循环
            if (attempts > 1000) {
                throw new IllegalStateException("Cannot find available position after 1000 attempts");
            }
        }
        return position;
    }

    /**
     * 每4字节的非线性混合
     */
    private int nonLinearMix(int hash) {
        // 采用S-BOX进行4-4置换
        int mixed = 0;
        for (int i = 0; i < 4; i++) {
            int nibble = (hash >>> (i * 8)) & 0xF;
            nibble = substitutionBox(nibble);
            mixed |= nibble << (i * 8 + 4);
        }

        // MurmurHash风格混合
        mixed ^= mixed >>> 16;
        mixed *= 0x85EBCA77;
        mixed ^= mixed >>> 13;
        mixed *= 0xC2B2AE35;
        mixed ^= mixed >>> 16;

        return mixed;
    }

    /**
     * 最终哈希增强
     */
    private int finalizeHash(int hash) {
        // 更多混合步骤
        hash ^= hash >>> 15;
        hash *= 0x65D54E3B;
        hash ^= hash >>> 11;

        // 确保正数
        return Math.abs(hash) & 0x7FFF_FFFF;
    }

    // 冲突解决使用的二次哈希函数
    private int rehash(int value) {
        value = (value ^ 0xDEADBEEF) * 0x9E3779B9;
        value = (value >> 16) ^ value;
        return value & 0xFFFF; // 返回0-65535之间的值
    }

    /**
     * 4位替代盒（S-BOX）提供非线性特性
     */
    private int substitutionBox(int nibble) {
        // 精心设计的密码学S-BOX
        final int[] sBox = {
                0xE, 0x3, 0xB, 0x8, 0x1, 0xC, 0xF, 0x0,
                0x7, 0x9, 0xA, 0x4, 0x6, 0x2, 0x5, 0xD
        };
        return sBox[nibble & 0xF];
    }

    public String generateNewNodeBefore(String existingNode) {
        // 1. 验证已有节点是否存在
        Integer existingPosition = findNodePosition(existingNode);
        if (existingPosition == null) {
            throw new IllegalArgumentException("Existing node not found: " + existingNode);
        }

        // 2. 获取前驱节点位置
        int predecessorPosition = getPredecessorPosition(existingNode);

        // 3. 生成满足位置要求的节点名称
        String newNodeName = null;
        int attempts = 0;
        boolean found = false;

        do {
            // 生成候选节点名称（使用UUID确保唯一性）
            String candidate = "node_" + UUID.randomUUID().toString().substring(0, 8);

            // 计算候选节点位置
            int candidatePosition = getDiscreteHash(candidate);

            // 检查是否在目标区间内
            if (isPositionBetween(candidatePosition, predecessorPosition, existingPosition)) {
                newNodeName = candidate;
                found = true;
            }

            attempts++;

            // 防止无限循环
            if (attempts > 100) {
                throw new IllegalStateException("Could not find suitable position after 100 attempts");
            }

        } while (!found);

        return newNodeName;
    }

    /**
     * 检查候选位置是否在指定区间内
     */
    private boolean isPositionBetween(int candidate, int start, int end) {
        // 正常情况：start < candidate < end
        if (start < end) {
            return candidate > start && candidate < end;
        }
        // 跨越环首尾的情况：candidate > start || candidate < end
        else {
            return candidate > start || candidate < end;
        }
    }

    public Collection<String> getNodes() {
        return ring.values();
    }

    public String getNode(String value) {
        if (ring.isEmpty()) {
            return null;
        }

        int hash = getDiscreteHash(value);

        // 查找大于或等于该哈希值的第一个节点
        Map.Entry<Integer, String> entry = ring.ceilingEntry(hash);

        if (entry == null) {
            // 如果没找到，返回环上的第一个节点（环行结构）
            entry = ring.firstEntry();
        }

        return entry.getValue();
    }


}